class Solution
{
public:
    int numSquares(int n)
    {
        vector<int> dp;
        dp.reserve(n + 1);
        dp.push_back(0);
        for (int i = 0; i <= n; ++i)
        {
            calc_dp(i, dp);
        }

        return dp[n];
    }

    int calc_dp(int n, vector<int> &cache)
    {
        if (n < cache.size())
        {
            return cache[n];
        }
        int minComp = n;
        int upper = floor(sqrt(n));
        for (int i = 1; i <= upper; ++i)
        {
            minComp = min(minComp, calc_dp(n - i * i, cache));
        }
        int result = minComp + 1;
        if (n == cache.size())
        {
            cache.push_back(result);
        }
        return result;
    }
};
